The present invention relates to authentication of concealed data without converting the data to its unconcealed form.
Note that the following discussion refers to a number of publications by author(s) and year of publication, and that due to recent publication dates certain publications are not to be considered as prior art vis-a-vis the present invention. Discussion of such publications herein is given for more complete background and is not to be construed as an admission that such publications are prior art for patentability determination purposes.
In many situations, it is desirable to authenticate data without revealing the data in detail. For instance, a party to a multilateral treaty might want to convince monitoring inspectors of the treaty that collected data represents a particular weapon type without revealing a detailed gamma spectrum of the weapon, which may in fact be classified. Even if the classified data can be kept private via an alternative representation, consistent correspondence between the classified and unclassified representations may reveal too much information about the weapon. As another example, the government may wish to utilize an information hiding mechanism to mitigate the concern of the private sector in providing proprietary information for national infrastructure protection.
Encryption alone cannot solve this problem. Additionally, certain data are prone to statistical variation, thus creating difficulties for consistent authentication results using standard digital authentication techniques. Gamma spectra are also examples of statistically variant data where measurements of the same sample with the same equipment will result in different spectra due to Poisson noise conditions.
Finally, public key cryptographic techniques are often useful in situations where one authenticating party seeks to convince multiple verifying parties or when the origination of data must be verifiable, thus providing non-repudiation. The present invention permits use of digital public key mechanisms to authenticate data prone to statistical variation and ability to hide data details while still proving the authenticity and integrity of the data.
Although the weapon inspection problem will be used as the primary exemplary application of the present invention, other applications exist with a similar problem set. For example, the use of biometrics (fingerprint, retina scan, voice patterns, etc.) to enable or authorize a certain function, such as entrance into a building, faces similar challenges. A biometric reading from the same individual using the same equipment will likely be slightly different each time. Moreover, the use of biometric information may have privacy implications that drive the need for hiding the detailed biometric information itself.
Generally speaking, any authentication process will have two steps. The first step is to initialize the authentication system by acquiring a reliable template of the item in question. In the weapon inspection application, this will be a representative weapon from the class of treaty-limited items. In the biometric application, initialization requires verification of the individual using information such as a birth certificate, driver's license, fingerprint, or deoxyribonucleic acid (DNA) sample, and acquisition of the initial biometric. The initialization step requires that the representative item (e.g., weapon or person) be certified to truly be a member of the class. This generally requires additional off-line inspection processes that will not be discussed further.
With the acquisition of an authentic template of monitored items, subsequent inspections can occur in the second part of the process. In the weapon authentication application, the basic problem is to make a class association as opposed to differentiating between individual weapons of the same class. In the biometric application, the original biometric is used as a template for subsequent authentication of the individual.
An approach developed for use in biometric identification utilizes error correction coding techniques. G. I. Davida, et al., “On Enabling Secure Applications Through Off-line Biometric Identification”, Proceedings of the IEEE Symposium on Security and Privacy, Oakland, Calif. (May 1998). It uses majority coding to construct a template of a biometric that is known to vary between measurements. Majority coding takes a number of measurements (preferably odd) and assigns each bit of the template to the value that is most often represented in the measurements using a majority rule. The template is then encoded into a code vector with a specified amount of redundancy. The amount of redundancy and the encoding technique used determines how many bits can be corrected in the template. In other words, if a vector does not perfectly match any codeword (template), then the closest codeword (in a Hamming sense) is generally assigned. The distance between codewords is representative of the number of correctable bits as well. A similar method is employed in U.S. Pat. No. 6,038,315, to Strait, et al., entitled “Method and System for Normalizing Biometric Variations to Authenticate Users from a Public Database and that Ensures Individual Biometric Data Privacy.”
During verification, the same majority coding technique is used to acquire a biometric representative from a number of measurements. Since majority coding is a bit-oriented technique, the idea is to use it to acquire a representative test biometric. The hope is that is it within a specified Hamming distance of the original biometric template. If the representative is close enough to the template, it can be decoded into the exact biometric using bounded distance decoding.
A speech scrambling invention uses a data hiding technique that is similar to the method described herein. V. Senk, et al., “A New Speech Scrambling Concept Based on Hadamard Matrices”, IEEE Signal Processing Letters 4(6): 161-163 (June 1997). However, the present invention constrains the input signal via scaling and centering prior to permuted transformation and they propose no authentication of the output signal. Scaling and centering of the input signal allows strong statements about the security of the invention. Independent of the permutation key and input spectrum, the output of the constrained permuted transform is consistent with a realization of Gaussian white noise. Hence, the distribution of the components of the output signal is substantially non-informative about the input signal.